The cloud computing model has attracted many businesses mainly due to its zero capital investment, flexibility as well as reduced operational cost. The model has changed the way companies do business into a utility model where one pays as per the usage. Computing as a service (CaaS) is an emerging branch of cloud computing where companies can utilize computational power and processing logics without needing to have licensed software copies, own processing logics and computing hardware setup in-house. One type of computation is that in a candidate for use in this way is tree-based classification. With the exponential growth of data, there is a real need to perform pattern recognition and mining on large data sets.
Even though CaaS provides many benefits, security and privacy concerns have still been the main factors keeping many companies from moving to the cloud. It is challenging to secure the input data since users need to allow the service provider to perform computations over the data without revealing them. Classification as a service has the added challenge of securing the classifier and the training set the service provider uses to train the tree.
Consider the following scenario. A user (client) has a set of images (X). The user may want to classify the images in order to determine whether they contain, for example, faces. The user does not have the resources and/or expertise to run a classification algorithm to classify them. Therefore, it wants to delegate the classification task f to a remote classifier (server in the cloud) and obtain the decision ƒ(x) where xεX. The following are the security and privacy requirements.                1. The user does not want to reveal the images (x values) to the classifier.        2. The classifier does not want to reveal its classification algorithm ƒ to the user, other than the information that can be inferred from ƒ(x).        3. The user does not want the classifier to learn the classification decision ƒ(x).        
Below is a short description of some of the computational primitives that are well-known in the art.
Computational Primitives
Oblivious Transfer
In 1-out-of-2 Oblivious Transfer (OT12), one party, the sender, has input composed of two strings (M0, M1), and the input of a second party, the chooser, is a bit σ. The chooser should learn Mσ and nothing regarding M1-σ, while the sender should gain no information about σ. 1-out-of-N OT is an extension of OT12 where the chooser learns one Mi(1≦i≦N) and nothing else. k-out-of-NOT is a generalization of OT1N. For more information, see M. O. Rabin, “How to Exchange Secrets with Oblivious Transfer,” Cryptology ePrint Archive, Report 2005/187, 2005, http://eprint.iacr.org/; S. Even, et al., “A Randomized Protocol for Signing Contracts,” Commun. ACM, 28(6):637-647, 1985; and M. Naor et al., “Efficient Oblivious Transfer Protocols,” In SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 448-457, Philadelphia, Pa., USA, 2001, Society for Industrial and Applied Mathematics.
Oblivious Polynomial Evaluation
An OPE protocol has two parties, the sender who has a polynomial ƒ over some finite field p and the receiver has an input xεp. At the end of the protocol, the receiver learns ƒ(x) and nothing else, and the sender learns nothing. For more information on OPE, see M. Naor, et al., “Oblivious Transfer and Polynomial Evaluation,” In STOC '99: Proceedings of the thirtyfirst annual ACM symposium on Theory of computing, pages 245-254, New York, N.Y., USA, 1999. ACM; H.-D. Li, et al., “Oblivious Polynomial Evaluation,” J. Comput. Sci. Technol., 19(4):550-554, 2004; M. Naor, et al., “Oblivious Polynomial Evaluation,” SIAM J. Comput., 35(5):1254-1281, 2006; and Y.-C. Chang, et al., “Oblivious Polynomial Evaluation and Oblivious Neural Learning, Theor. Comput. Sci., 341(1):39-54, 2005.
Homomorphic Encryption
An asymmetric cryptosystem—which consists of key generation, encryption (E) and decryption (D) functions—is homomorphic if for any given public key and any two plaintext messages m1, m2 in the plaintext space, the following encryption relationship holds:E(m1⊙m2)=E(m1)⊙E(m2),where ⊙ is a binary operator. If the operator is addition, the cryptosystem is additive homomorphic (e.g., P. Paillier, “Public-Key Cryptosystems Based On Composite Degree Residuosity Classes,” In EUROCRYPT '99: Proceedings of the 17th international conference on Theory and application of cryptographic techniques, pages 223-238, Berlin, Heidelberg, 1999, Springer-Verlag) and if the operator is multiplication, the cryptosystem is multiplicative homomorphic (e.g., T. El Gamal, “A Public Key Cryptosystem and a Signature Scheme Based On Discrete Logarithms,” In Proceedings of CRYPTO 84 on Advances in cryptology, pages 10-18, New York, N.Y., USA, 1985. Springer-Verlag New York, Inc.).Oblivious Transfer
All known OT protocols require public key cryptography (PKC). PKC involves modular exponentiation. Hence, the computation overhead is more demanding than its communication overhead. Herein, implementations of OT12 and OT1N are described which closely follows the protocols proposed by Naor and Pinkas, “Efficient Oblivious Transfer Protocols,” In SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 448-457, Philadelphia, Pa., USA, 2001. Society for Industrial and Applied Mathematics.
1-Out-of-2 Oblivious Transfer
The chooser's input is σε0, 1, and the sender's input is two strings M0, M1. The chooser's output is Mσ. The protocol operates over a group q of prime order and g is a generator of the group. The construction uses a function H that is modeled as a random oracle, i.e. chosen as a truly random function available to any participant and usually implemented as a hash function such as SHA.
The Protocol Using ElGamal Encryption
                1. The sender chooses a random element rsεq and publishes it.        2. The chooser picks a random rcεq and sets the public keys PKσ=grc and PK1-σ=rs/PKσ and sends PK0 to the sender.        3. The sender computes PK1=rs/PK0 and chooses randoms r1, r2εq. It encrypts M0 by E0 as the tuple gr0,H(PK0r0)⊕M0, where ⊕ is a bit-wise binary operator, and encrypts E1=gr1,H(PK1r1)⊕M1, and sends them to the chooser.        4. The chooser computes H((grσ)rc)=H(PKσrσ) and uses it to decrypt Mσ.        
The same r=r1=r2 can be used to provide the same level of privacy and security. With the same r, the sender needs to compute three exponentiations (one of them can be precomputed before the protocol begins) and the chooser needs to compute two exponentiations (one of them can be precomputed). Assuming q is a n-bit prime number, the communication complexity is 2n (from chooser)+n+2 log2|M| (from sender). The complexity is 5n if messages are elements of q and one random value r is used.
Oblivious Polynomial Evaluation
The OPE protocol introduced by Chang and Lu, “Oblivious Polynomial Evaluation and Oblivious Neural Learning,” Theor. Comput. Sci., 341(1):39-54, 2005, employs OT12.
The polynomials are over a finite field q where q is a an l-bit prime number. The receiver has the input x*εq and the sender has the polynomial of degree d, ƒ(x)=Σi=0daixi.
Each coefficient ai is represented as follows:
                                          a            i                    =                                    ∑                              j                =                1                            l                        ⁢                                                  ⁢                                          a                ij                            ⁢                              2                                  j                  -                  1                                                                    ,                              a            ij                    ∈                      {                          0              ,              1                        }                                              (        1        )            
For each iε[1, d] and each jε[1,l], the receiver computes the value vij as follows:vij=2j-1x*i.
Notice that for each iε[1, d] the following holds:
            ∑              j        =        1            l        ⁢                  ⁢                  a        ij            ⁢              v        ij              =            a      i        ⁢                  x        *        i            .      
The protocol using OT12:                1. The receiver prepares dl pairs of (rij, vij+rij) where each rij is chosen uniformly at random from q.        2. For each pair of (rij, vij+rij), the sender runs an OT12 with the receiver to get rij if aij=0 and vij+rij otherwise.        3. The sender computes the sum of a0 and the output of the dl OT12 protocols which is equal to a0+Σi=1dΣj=1l(aijvij+rij)=ƒ(x*)+Σi,jrij. The receiver subtracts Σi,jrij from sender's output and obtains ƒ(x*).        
The dominant operation in this protocol is the OT12 operations. The complexity is dl times that of OT12. (Five exponentiation and three inverse operations per OT12).
The protocol using additive homomorphic encryption (HE) is as follows:                1. The receiver prepares dl values of E(vij).        2. For each value of Eij, the sender picks 1 if aij=0 and E(vij) otherwise.        3. The sender computes the sum of a0 and the output of the dl encrypted values which is equal to E(a0)×Πi=1dΠj=1lEij=E(ƒ(x*)). The receiver decrypts and obtains ƒ(x*).        
The dominant operation in this protocol is the HE operations. The complexity is 2dl times that of encryption (i.e., one exponentiation per encryption). Compared to the first protocol, the number of exponentiations in the second approach is reduced by half. Compared to the first protocol and assuming that the ciphertext space is same as the plaintext space, the communication complexity in the second approach is reduced by two thirds.
Additional techniques related to those described above include privacy preserving data mining (PPDM). In PPDM research, the main focus has been to collectively learn a predictive model while addressing privacy and security concerns. In such research, there are two main branches of problems. The final goal of both branches is to train a predictive model, but the two branches make different assumptions and have different settings. The first category (perturbed input problem) addresses the problem of keeping the input to the data mining party, i.e., the classifier, private and creating the predictive model. The second category (private party input problem) address the following problem: there are several parties having input data and they collectively want to create a predictive model while each party keeping their input data private for the other involving parties.
In the private party input problem, the input data from different parties could be either horizontally or vertically partitioned. With horizontally partitioned data, each party has complete data sets for all the features under consideration. In contrast, with vertically partitioned data, each party does not have complete data sets for the features under consideration, i.e., each has partial input data to construct complete data sets. In the ideal situation, at the end of the data mining procedure, each party knows only their data, vertically or horizontally partitioned, and the trained predictive model.
In the perturbed input problem, as the name suggests, the user, that owns the input data, adds “noise” (e.g., generalization, distortion, etc.) to the data before the data mining process and then use reconstruction techniques to recover the original cumulative distribution (not the original values). The noise hides the data from the classifier. However, it is difficult to quantify the level of privacy and security that such a method provides. Further, the predictive model has some amount of false positives as well as negatives due to the noise. After learning the predictive model from the perturbed data, the model can classify non-perturbed data. In order to protect user inputs, the user is given the predictive model to locally run the classification algorithm. While such an approach preserve the privacy of the user inputs, it fails to protect the predictive model.